#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-10-27 8:50 上午
# @Author  : yangdy
# @File    : 2020-10-27.144.二叉树的前序遍历
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
            ans = []
            cur, stack = root, []
            while cur or stack:
                while cur:
                    stack.append(cur)
                    ans.append(cur.val)
                    cur = cur.left
                cur = stack.pop()
                cur = cur.right
            return ans
